package cn.edu.zufe.mjt.dp;


/**
 * 动态规划 —— 零钱兑换问题
 * 问题描述：给定--个整数序列 coins,其中coins[i]表示一个面额为coins[i]的硬币;
 * 在给定一个整数amount,表示需要组成的总金额。
 * 请你计算组成该金额所需的最少硬币个数。
 * 如果没有任何一种硬币组合能凑成该金额，返回-1
 */
public class CashChange {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5, 10, 20, 50};
         int amount = 11;
        int ints = minCoins(coins, amount);
        System.out.println(ints);
    }

    public static int minCoins(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        for (int i = 1; i <= amount; i++) {
            int min = Integer.MAX_VALUE;
            for (int coin : coins) {
                if (coin <= i) {
                    int subRes = dp[i - coin];
                    if (subRes != Integer.MAX_VALUE && subRes + 1 < min) {
                        min = subRes + 1;
                    }
                }
            }
            dp[i] = min;
        }
        return dp[amount] == Integer.MAX_VALUE? -1 : dp[amount];
    }
}
